
\begin{frame}
	\frametitle{LMT Algorithmus}
	
	\huge
	Ziel: Finde alle Kanten, die definitiv Teil der MWT sind.
	\vspace{0.5cm}
	
	\normalsize
	Daf\"ur drei Schritte:
	\begin{enumerate}
		\item Alle m\"oglichen Kanten erzeugen und speichern.
		\item Alle Kanten, die definitiv nicht dabei sind, entfernen.
	\item Kanten finden, die auf jeden Fall Teil der MWT sind.
	\end{enumerate}
\end{frame}

\begin{frame}
	\frametitle{LMT Algorithmus: Schritt 1/3 - Erzeugung}

	\vspace{0.4cm}
	\includegraphics[height=4cm]{me_point_set.png}
	\vspace{0.4cm}
	
	\huge
	Die Eingabe ist eine Punktmenge auf einer X-Y Fl\"ache.
	
\end{frame}

\begin{frame}
	\frametitle{LMT Algorithmus: Schritt 1/3 - Erzeugung}

	\vspace{0.4cm}
	\includegraphics[height=4cm]{me_point_set_connected.png}
	\vspace{0.4cm}
	
	\begin{itemize}
	\item alle Knoten werden untereinander mit Kanten verbunden\\
	$\rightarrow$ \emph{candidateEdges}
	\end{itemize}
	
\end{frame}

\begin{frame}
	\frametitle{LMT Algorithmus: Schritt 1/3 - Erzeugung}

	\vspace{0.4cm}
	\hspace{3.0cm}
	\includegraphics[height=4cm]{me_tri_generation.png}
	\vspace{0.4cm}
	
	\begin{itemize}
	\item \emph{triangles} = set.generateTriangles()
	\item Erzeugen aller durch Kanten geformte Dreicke
	\item Jede Kante h\"alt eine Liste von angrenzenden Dreiecken
	\end{itemize}
	
\end{frame}

\begin{frame}
	\frametitle{LMT Algorithmus: Schritt 1/3 - Erzeugung}

	\vspace{0.4cm}
	\hspace{3.0cm}
	\includegraphics[height=4cm]{me_convex_hull.png}
	\vspace{0.4cm}
	
	\begin{itemize}
	\item Kanten aus der konvexen H\"ulle sind definitiv Teil der MWT
	\item in \emph{edgesInMWT} speichern wir alle Kanten, die Teil der MWT sind
	\item Kanten der konvexen H\"ulle werden deswegen in diese Liste eingef\"ugt
	\end{itemize}
	
\end{frame}

\begin{frame}
	\frametitle{LMT Algorithmus: Schritt 2/3 - Entfernen}

	\huge
	Schritt 2: Jetzt wollen wir alle Kanten finden, die sicher nicht Teil der MWT sind, um diese aus der Liste der candidate edges zu entfernen.
	
\end{frame}

\begin{frame}
	\frametitle{LMT Algorithmus: Schritt 2/3 - Entfernen}

	\huge
	Local Minimality:
	
	\normalsize
	\vspace{0.1cm}
	\hspace{2.0cm}
	\includegraphics[height=4cm]{me_local_minimal.png}
	\vspace{0.2cm}
	
	\huge
	Eine Kante ist lokal minimal, wenn sie in einem Dreieckspaar nicht geflipped werden kann, um das Gewicht von den Dreiecken zu reduzieren.
	
\end{frame}

\begin{frame}
	\frametitle{LMT Algorithmus: Schritt 2/3 - Entfernen}

	\vspace{0.1cm}
	\hspace{3.0cm}
	\includegraphics[height=4cm]{me_never_locally_minimal.png}
	\vspace{0.2cm}
	
	\normalsize
	\begin{itemize}
	\item alle Kanten haben angrenzende Dreiecke
	\item eine Kante ist definitiv nicht Teil der MWT, falls sie in in keinem betroffenen Dreieckspaar lokal minimal ist
	\item w\"are sie teil der MWT, k\"onnte man durch flippen dieser das Gesamtgewicht reduzieren
	\end{itemize}
\end{frame}

\begin{frame}
	\frametitle{LMT Algorithmus: Schritt 2/3 - Entfernen}

	\huge
	Also entfernen wir alle diese Kanten:

	\normalsize
	\vspace{-2cm}
	\hspace{-2.1cm}  
	\includegraphics<1>[scale=0.65]{source_code.pdf}
	\hspace{1cm}
	
\end{frame}

\begin{frame}
	\frametitle{LMT Algorithmus: Schritt 3/3 - W\"ahlen}

	\huge
	Schritt 3: Alle Kanten, die sicher nicht Teil der MWT sind, wurden entfernt. Im n\"achsten Schritt sollen die Kanten selektiert werden, die sicher in der MWT sind.
	
\end{frame}


\begin{frame}
	\frametitle{LMT Algorithmus: Schritt 3/3 - W\"ahlen}
	
	\vspace{0.1cm}
	\hspace{3.0cm}
	\includegraphics[height=4cm]{me_never_locally_minimal.png}
	\vspace{0.2cm}
	
	\huge
	Wenn wir eine Kante haben, die Teil aller lokal minimalen Triangulierungen ist, dann ist sie auch Teil der MWT.
	
\end{frame}


\begin{frame}
	\frametitle{LMT Algorithmus: Schritt 3/3 - W\"ahlen}
	
	\vspace{0.1cm}
	\hspace{2.0cm}
	\includegraphics[height=4cm]{me_intersection.png}
	\vspace{0.2cm}
	
	\normalsize
	Kriterium: Wird die Kante von einer anderen Kante \"uberschnitten? Wenn nein, dann ist sie in allen lokal minimalen Triangulierungen, und ist dann Teil der MWT
	
\end{frame}


\begin{frame}
	\frametitle{LMT Algorithmus: Schritt 3/3 - W\"ahlen}
	
	\huge
	Diese Kanten werden in die $edgesInMWT$ Liste eingef\"ugt, und es wird nochmals alles von vorne gemacht. Dies wird wiederholt, bis sich keine Kanten mehr \"andern.
	
\end{frame}
